Strings
using System;
using System.Collections.Generic;
namespace algorithms.strings
{
// ----- Boyer Moore Search ------------------------------------------------
//
// An efficient string searching algorithm
//
// O(nm) in the worst case
//
// BoyerMooreSearch()
// BoyerMooreSearch(int alphabetSize, Func<char, byte> alphabetFunc)
// int Search(string text, string pattern)
// IEnumerable<int> SearchAll(string text, string pattern)
// -------------------------------------------------------------------------
public class BoyerMooreSearch
{
private int alphabetSize = 0;
Func<char, byte> alphabetFunc = null;
private int[] occurenceFunc = null;
public BoyerMooreSearch() : this(26, p => (byte)(Convert.ToByte(p) - 97)) { }
public BoyerMooreSearch(int alphabetSize, Func<char, byte> alphabetFunc)
{
this.alphabetSize = alphabetSize;
this.alphabetFunc = alphabetFunc;
occurenceFunc = new int[alphabetSize];
}
public int Search(string text, string pattern)
{
int tLen = text.Length;
int pLen = pattern.Length;
for (int i = 0; i < alphabetSize; i++) occurenceFunc[i] = -1;
for (int i = 0; i < pLen; i++) occurenceFunc[alphabetFunc(pattern[i])] = i;
int[] f = new int[pLen + 1];
int[] s = new int[pLen + 1];
int i1 = pLen, i2 = pLen + 1;
f[i1] = i2;
while (i1 > 0)
{
while (i2 <= pLen && pattern[i1 - 1] != pattern[i2 - 1])
{
if (s[i2] == 0)
{
s[i2] = i2 - i1;
}
i2 = f[i2];
}
i1--; i2--;
f[i1] = i2;
}
i2 = f[0];
for (i1 = 0; i1 <= pLen; i1++)
{
if (s[i1] == 0) s[i1] = i2;
if (i1 == i2) i2 = f[i2];
}
i1 = 0;
while (i1 <= tLen - pLen)
{
i2 = pLen - 1;
while (i2 >= 0 && pattern[i2] == text[i1 + i2]) i2--;
if (i2 < 0)
{
return i1;
}
else
i1 += Math.Max(s[i2 + 1], i2 - occurenceFunc[alphabetFunc(text[i1 + i2])]);
}
return -1;
}
public IEnumerable<int> SearchAll(string text, string pattern)
{
int tLen = text.Length;
int pLen = pattern.Length;
for (int i = 0; i < alphabetSize; i++) occurenceFunc[i] = -1;
for (int i = 0; i < pLen; i++) occurenceFunc[alphabetFunc(pattern[i])] = i;
int[] f = new int[pLen + 1];
int[] s = new int[pLen + 1];
int i1 = pLen, i2 = pLen + 1;
f[i1] = i2;
while (i1 > 0)
{
while (i2 <= pLen && pattern[i1 - 1] != pattern[i2 - 1])
{
if (s[i2] == 0)
{
s[i2] = i2 - i1;
}
i2 = f[i2];
}
i1--; i2--;
f[i1] = i2;
}
i2 = f[0];
for (i1 = 0; i1 <= pLen; i1++)
{
if (s[i1] == 0) s[i1] = i2;
if (i1 == i2) i2 = f[i2];
}
i1 = 0;
while (i1 <= tLen - pLen)
{
i2 = pLen - 1;
while (i2 >= 0 && pattern[i2] == text[i1 + i2]) i2--;
if (i2 < 0)
{
yield return i1;
i1 += s[0];
}
else
i1 += Math.Max(s[i2 + 1], i2 - occurenceFunc[alphabetFunc(text[i1 + i2])]);
}
}
}
}
using System.Linq;
namespace algorithms.strings
{
public static class LongestCommonPrefixArray
{
// ----- Longest Common Prefix Array -----------------------------------
// An auxiliary data structure to the suffix array
//
// Stores the lengths of the longest common prefixes (LCPs) between
// all pairs of consecutive suffixes in a sorted suffix array
//
// O(n) worst-case time and space
//
// Dependencies:
// -- Suffix Array
//
// int[] LCP(char[] S, int[] suffixArray)
// ---------------------------------------------------------------------
public static int[] LCP(char[] S, int[] suffixArray)
{
int n = S.Length;
int h = 0;
int[] lcp = new int[n];
int[] isa = new int[n];
for (int i = 0; i < n; i++) isa[suffixArray[i]] = i;
for (int i = 0; i < n; i++)
{
if (isa[i] > 0)
{
for (int j = suffixArray[isa[i] - 1]; j + h < n && i + h < n && S[j + h] == S[i + h]; h++) ;
lcp[isa[i]] = h;
}
else
{
lcp[isa[i]] = 0;
}
if (h > 0) h--;
}
return lcp;
}
public static int[] LCP(string S, int[] suffixArray)
{
return LCP(S.ToArray(), suffixArray);
}
// ---------------------------------------------------------------------
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace algorithms.strings
{
public static class Palindromes
{
// ----- Palindromes ---------------------------------------------------
//
// IEnumerable<string> Palindromes_01(string s)
// int[] Palindromes_02(string s)
// IEnumerable<string> Palindromes_02(string s, int[] r)
// int number_of_palindromic_subsequences(string s)
// ---------------------------------------------------------------------
public static IEnumerable<string> Palindromes_01(string s)
{
int radius = 0;
int N = s.Length;
int[,] pTable = new int[2, N + 1];
s = "@" + s + "#";
for (int j = 0; j <= 1; j++)
{
radius = 0;
pTable[j, 0] = 0;
int i = 1;
while (i <= N)
{
while (s[i - radius - 1] == s[i + j + radius]) radius++;
pTable[j, i] = radius;
int k = 1;
while ((pTable[j, i - k] != radius - k) && (k < radius))
{
pTable[j, i + k] = Math.Min(pTable[j, i - k], radius - k);
k++;
}
radius = Math.Max(radius - k, 0);
i += k;
}
}
s = s.Substring(1, N);
for (int i = 1; i <= N; i++)
for (int j = 0; j <= 1; j++)
for (int rp = pTable[j, i]; rp > 0; rp--)
yield return s.Substring(i - rp - 1, 2 * rp + j);
}
public static int[] Palindromes_02(string s)
{
int n = s.Length;
int[] r = new int[2 * n];
int k = 0;
for (int i = 0, j = 0; i < 2 * n; i += k, j = Math.Max(j - k, 0))
{
while (i - j >= 0 && i + j + 1 < 2 * n && s[(i - j) / 2] == s[(i + j + 1) / 2]) j++;
r[i] = j;
for (k = 1; i - k >= 0 && r[i] - k >= 0 && r[i - k] != r[i] - k; k++)
{
r[i + k] = Math.Min(r[i - k], r[i] - k);
}
}
return r;
}
public static IEnumerable<string> Palindromes_02(string s, int[] r)
{
for (int i = 0; i < r.Length / 2; i++)
{
yield return s.Substring(i - r[i * 2] / 2, r[i * 2]);
if (r[i * 2 + 1] > 0)
yield return s.Substring(i + 1 - r[i * 2 + 1] / 2, r[i * 2 + 1]);
}
}
// ---------------------------------------------------------------------
static int[,] nops_gg = null;
static string nops_S = null;
static int nops_R = 1000 * 1000 * 1000 + 7;
static int nops_G(int ix, int len)
{
if (ix >= nops_S.Length) return 0;
if (len <= 0) return 0;
if (len == 1) return 1;
if (nops_gg[ix, len] != -1) return nops_gg[ix, len];
int g = (nops_G(ix + 1, len - 1) + nops_G(ix, len - 1) - nops_G(ix + 1, len - 2) + (nops_S[ix] == nops_S[ix + len - 1] ? 1 : 0) * (1 + nops_G(ix + 1, len - 2))) % nops_R;
nops_gg[ix, len] = g;
return g;
}
public static int number_of_palindromic_subsequences(string s)
{
int n = s.Length;
nops_gg = new int[n, n + 1];
for (int i = 0; i < n; i++)
for (int j = 0; j < n + 1; j++)
nops_gg[i, j] = -1;
nops_S = s;
return nops_G(0, n);
}
// ---------------------------------------------------------------------
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace algorithms.strings
{
public class PalindromicTree
{
const int MAXN = 105000;
struct Node
{
public int[] Next { get; set; }
public int Len { get; set; }
public int SuffLink { get; set; }
public int Num { get; set; }
};
int len;
char[] s = new char[MAXN];
Node[] tree = new Node[MAXN];
int num; // node 1 - root with len -1, node 2 - root with len 0
int suff; // max suffix palindrome
long ans;
bool addLetter(int pos)
{
int cur = suff, curlen = 0;
int let = s[pos] - 'a';
while (true)
{
curlen = tree[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
break;
cur = tree[cur].sufflink;
}
if (tree[cur].next[let])
{
suff = tree[cur].next[let];
return false;
}
num++;
suff = num;
tree[num].len = tree[cur].len + 2;
tree[cur].next[let] = num;
if (tree[num].len == 1)
{
tree[num].sufflink = 2;
tree[num].num = 1;
return true;
}
while (true)
{
cur = tree[cur].sufflink;
curlen = tree[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
{
tree[num].sufflink = tree[cur].next[let];
break;
}
}
tree[num].num = 1 + tree[tree[num].sufflink].num;
return true;
}
void initTree()
{
num = 2; suff = 2;
tree[1].len = -1; tree[1].sufflink = 1;
tree[2].len = 0; tree[2].sufflink = 1;
}
}
}
using System;
namespace algorithms.strings
{
public static class Searching
{
// ----- Searching -----------------------------------------------------
//
// Search with Suffix Array
// http://www.inf.fu-berlin.de/lehre/WS05/aldabi/downloads/stringMatching_part2.pdf
//
// O(mlogn)
//
// Dependencies:
// -- Suffix Array
//
// int SearchSA(char[] S, int[] suffixArray, char[] pattern, out int L, out int R)
// ---------------------------------------------------------------------
static int CompareSA(char[] pattern, char[] S, int ix)
{
for (int i = 0; i < Math.Min(S.Length - ix, pattern.Length); i++)
if (pattern[i] != S[ix + i])
return pattern[i].CompareTo(S[ix + i]);
if (pattern.Length > S.Length) return 1;
return 0;
}
public static int SearchSA(char[] S, int[] suffixArray, char[] pattern, out int Lp, out int Rp)
{
int N = S.Length;
if (CompareSA(pattern, S, suffixArray[0]) <= 0) Lp = 0;
else
if (CompareSA(pattern, S, suffixArray[N - 1]) > 0) Lp = N;
else
{
int L = 0;
int R = N - 1;
while (R - L > 1)
{
int M = (L + R + 1) / 2;
if (CompareSA(pattern, S, suffixArray[M]) <= 0) R = M; else L = M;
}
Lp = R;
}
if (CompareSA(pattern, S, suffixArray[0]) < 0) Rp = -1;
else
if (CompareSA(pattern, S, suffixArray[N - 1]) >= 0) Rp = N - 1;
else
{
int L = 0;
int R = N - 1;
while (R - L > 1)
{
int M = (L + R + 1) / 2;
if (CompareSA(pattern, S, suffixArray[M]) >= 0) L = M; else R = M;
}
Rp = L;
}
return Rp - Lp + 1;
}
// ---------------------------------------------------------------------
}
}
using System.Linq;
namespace algorithms.strings
{
public static class SuffixArray
{
// ----- Suffix Array --------------------------------------------------
//
// SAIS - the induced sorting based suffix array construction algorithm
//
// "sorted array of all substrings"
//
// O(n) worst-case time
// MAX(2n, 4k) worst-case extra working space
// n and k are the length of the input string and the size of alphabet
//
// https://sites.google.com/site/yuta256/sais
//
// int[] SA(byte[] T)
// int[] SA(char[] T)
// int[] SA(int[] T, int alphabetSize)
// int[] SA(string T)
// ---------------------------------------------------------------------
interface BaseArray
{
int this[int index] { get; set; }
}
class ByteArray : BaseArray
{
byte[] _arr;
int _ofs;
public ByteArray(byte[] arr, int ofs)
{
_arr = arr;
_ofs = ofs;
}
public int this[int index]
{
get { return (int)_arr[_ofs + index]; }
set { _arr[_ofs + index] = (byte)value; }
}
}
class CharArray : BaseArray
{
char[] _arr;
int _ofs;
public CharArray(char[] arr, int ofs)
{
_arr = arr;
_ofs = ofs;
}
public int this[int index]
{
get { return (int)_arr[_ofs + index]; }
set { _arr[_ofs + index] = (char)value; }
}
}
class IntArray : BaseArray
{
int[] _arr;
int _ofs;
public IntArray(int[] arr, int ofs)
{
_arr = arr;
_ofs = ofs;
}
public int this[int index]
{
get { return _arr[_ofs + index]; }
set { _arr[_ofs + index] = value; }
}
}
const int MINBUCKETSIZE = 256;
static void GetCounts(BaseArray T, BaseArray C, int n, int k)
{
int i;
for (i = 0; i < k; ++i) { C[i] = 0; }
for (i = 0; i < n; ++i) { C[T[i]] = C[T[i]] + 1; }
}
static void GetBuckets(BaseArray C, BaseArray B, int k, bool end)
{
int i, sum = 0;
if (end != false) { for (i = 0; i < k; ++i) { sum += C[i]; B[i] = sum; } }
else { for (i = 0; i < k; ++i) { sum += C[i]; B[i] = sum - C[i]; } }
}
static void LMSSort(BaseArray T, int[] SA, BaseArray C, BaseArray B, int n, int k)
{
int b, i, j;
int c0, c1;
if (C == B) { GetCounts(T, C, n, k); }
GetBuckets(C, B, k, false);
j = n - 1;
b = B[c1 = T[j]];
--j;
SA[b++] = (T[j] < c1) ? ~j : j;
for (i = 0; i < n; ++i)
{
if (0 < (j = SA[i]))
{
if ((c0 = T[j]) != c1) { B[c1] = b; b = B[c1 = c0]; }
--j;
SA[b++] = (T[j] < c1) ? ~j : j;
SA[i] = 0;
}
else if (j < 0)
{
SA[i] = ~j;
}
}
if (C == B) { GetCounts(T, C, n, k); }
GetBuckets(C, B, k, true);
for (i = n - 1, b = B[c1 = 0]; 0 <= i; --i)
{
if (0 < (j = SA[i]))
{
if ((c0 = T[j]) != c1) { B[c1] = b; b = B[c1 = c0]; }
--j;
SA[--b] = (T[j] > c1) ? ~(j + 1) : j;
SA[i] = 0;
}
}
}
static int LMSPostProc(BaseArray T, int[] SA, int n, int m)
{
int i, j, p, q, plen, qlen, name;
int c0, c1;
bool diff;
for (i = 0; (p = SA[i]) < 0; ++i) { SA[i] = ~p; }
if (i < m)
{
for (j = i, ++i; ; ++i)
{
if ((p = SA[i]) < 0)
{
SA[j++] = ~p; SA[i] = 0;
if (j == m) { break; }
}
}
}
i = n - 1; j = n - 1; c0 = T[n - 1];
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) >= c1));
for (; 0 <= i;)
{
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) <= c1));
if (0 <= i)
{
SA[m + ((i + 1) >> 1)] = j - i; j = i + 1;
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) >= c1));
}
}
for (i = 0, name = 0, q = n, qlen = 0; i < m; ++i)
{
p = SA[i]; plen = SA[m + (p >> 1)]; diff = true;
if ((plen == qlen) && ((q + plen) < n))
{
for (j = 0; (j < plen) && (T[p + j] == T[q + j]); ++j) { }
if (j == plen) { diff = false; }
}
if (diff != false) { ++name; q = p; qlen = plen; }
SA[m + (p >> 1)] = name;
}
return name;
}
static void InduceSA(BaseArray T, int[] SA, BaseArray C, BaseArray B, int n, int k)
{
int b, i, j;
int c0, c1;
if (C == B) { GetCounts(T, C, n, k); }
GetBuckets(C, B, k, false);
j = n - 1;
b = B[c1 = T[j]];
SA[b++] = ((0 < j) && (T[j - 1] < c1)) ? ~j : j;
for (i = 0; i < n; ++i)
{
j = SA[i]; SA[i] = ~j;
if (0 < j)
{
if ((c0 = T[--j]) != c1) { B[c1] = b; b = B[c1 = c0]; }
SA[b++] = ((0 < j) && (T[j - 1] < c1)) ? ~j : j;
}
}
if (C == B) { GetCounts(T, C, n, k); }
GetBuckets(C, B, k, true);
for (i = n - 1, b = B[c1 = 0]; 0 <= i; --i)
{
if (0 < (j = SA[i]))
{
if ((c0 = T[--j]) != c1) { B[c1] = b; b = B[c1 = c0]; }
SA[--b] = ((j == 0) || (T[j - 1] > c1)) ? ~j : j;
}
else
{
SA[i] = ~j;
}
}
}
static int ComputeBWT(BaseArray T, int[] SA, BaseArray C, BaseArray B, int n, int k)
{
int b, i, j, pidx = -1;
int c0, c1;
if (C == B) { GetCounts(T, C, n, k); }
GetBuckets(C, B, k, false);
j = n - 1;
b = B[c1 = T[j]];
SA[b++] = ((0 < j) && (T[j - 1] < c1)) ? ~j : j;
for (i = 0; i < n; ++i)
{
if (0 < (j = SA[i]))
{
SA[i] = ~(c0 = T[--j]);
if (c0 != c1) { B[c1] = b; b = B[c1 = c0]; }
SA[b++] = ((0 < j) && (T[j - 1] < c1)) ? ~j : j;
}
else if (j != 0)
{
SA[i] = ~j;
}
}
if (C == B) { GetCounts(T, C, n, k); }
GetBuckets(C, B, k, true);
for (i = n - 1, b = B[c1 = 0]; 0 <= i; --i)
{
if (0 < (j = SA[i]))
{
SA[i] = (c0 = T[--j]);
if (c0 != c1) { B[c1] = b; b = B[c1 = c0]; }
SA[--b] = ((0 < j) && (T[j - 1] > c1)) ? ~((int)T[j - 1]) : j;
}
else if (j != 0)
{
SA[i] = ~j;
}
else
{
pidx = i;
}
}
return pidx;
}
static int SAISMain(BaseArray T, int[] SA, int fs, int n, int k, bool isbwt)
{
BaseArray C, B, RA;
int i, j, b, m, p, q, name, pidx = 0, newfs;
int c0, c1;
uint flags = 0;
if (k <= MINBUCKETSIZE)
{
C = new IntArray(new int[k], 0);
if (k <= fs) { B = new IntArray(SA, n + fs - k); flags = 1; }
else { B = new IntArray(new int[k], 0); flags = 3; }
}
else if (k <= fs)
{
C = new IntArray(SA, n + fs - k);
if (k <= (fs - k)) { B = new IntArray(SA, n + fs - k * 2); flags = 0; }
else if (k <= (MINBUCKETSIZE * 4)) { B = new IntArray(new int[k], 0); flags = 2; }
else { B = C; flags = 8; }
}
else
{
C = B = new IntArray(new int[k], 0);
flags = 4 | 8;
}
GetCounts(T, C, n, k); GetBuckets(C, B, k, true);
for (i = 0; i < n; ++i) { SA[i] = 0; }
b = -1; i = n - 1; j = n; m = 0; c0 = T[n - 1];
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) >= c1));
for (; 0 <= i;)
{
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) <= c1));
if (0 <= i)
{
if (0 <= b) { SA[b] = j; }
b = --B[c1]; j = i; ++m;
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) >= c1));
}
}
if (1 < m)
{
LMSSort(T, SA, C, B, n, k);
name = LMSPostProc(T, SA, n, m);
}
else if (m == 1)
{
SA[b] = j + 1;
name = 1;
}
else
{
name = 0;
}
if (name < m)
{
if ((flags & 4) != 0) { C = null; B = null; }
if ((flags & 2) != 0) { B = null; }
newfs = (n + fs) - (m * 2);
if ((flags & (1 | 4 | 8)) == 0)
{
if ((k + name) <= newfs) { newfs -= k; }
else { flags |= 8; }
}
for (i = m + (n >> 1) - 1, j = m * 2 + newfs - 1; m <= i; --i)
{
if (SA[i] != 0) { SA[j--] = SA[i] - 1; }
}
RA = new IntArray(SA, m + newfs);
SAISMain(RA, SA, newfs, m, name, false);
RA = null;
i = n - 1; j = m * 2 - 1; c0 = T[n - 1];
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) >= c1));
for (; 0 <= i;)
{
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) <= c1));
if (0 <= i)
{
SA[j--] = i + 1;
do { c1 = c0; } while ((0 <= --i) && ((c0 = T[i]) >= c1));
}
}
for (i = 0; i < m; ++i) { SA[i] = SA[m + SA[i]]; }
if ((flags & 4) != 0) { C = B = new IntArray(new int[k], 0); }
if ((flags & 2) != 0) { B = new IntArray(new int[k], 0); }
}
if ((flags & 8) != 0) { GetCounts(T, C, n, k); }
if (1 < m)
{
GetBuckets(C, B, k, true);
i = m - 1; j = n; p = SA[m - 1]; c1 = T[p];
do
{
q = B[c0 = c1];
while (q < j) { SA[--j] = 0; }
do
{
SA[--j] = p;
if (--i < 0) { break; }
p = SA[i];
} while ((c1 = T[p]) == c0);
} while (0 <= i);
while (0 < j) { SA[--j] = 0; }
}
if (isbwt == false) { InduceSA(T, SA, C, B, n, k); }
else { pidx = ComputeBWT(T, SA, C, B, n, k); }
C = null; B = null;
return pidx;
}
static int SufSort(byte[] T, int[] SA, int n)
{
if ((T == null) || (SA == null) || (T.Length < n) || (SA.Length < n)) { return -1; }
if (n <= 1) { if (n == 1) { SA[0] = 0; } return 0; }
return SAISMain(new ByteArray(T, 0), SA, 0, n, 256, false);
}
static int SufSort(char[] T, int[] SA, int n)
{
if ((T == null) || (SA == null) || (T.Length < n) || (SA.Length < n)) { return -1; }
if (n <= 1) { if (n == 1) { SA[0] = 0; } return 0; }
return SAISMain(new CharArray(T, 0), SA, 0, n, 128, false);
}
static int SufSort(int[] T, int[] SA, int n, int alphabetSize)
{
if ((T == null) || (SA == null) || (T.Length < n) || (SA.Length < n)) { return -1; }
if (n <= 1) { if (n == 1) { SA[0] = 0; } return 0; }
return SAISMain(new IntArray(T, 0), SA, 0, n, alphabetSize, false);
}
public static int[] SA(byte[] T)
{
int n = T.Length;
int[] sa = new int[n];
SufSort(T, sa, n);
return sa;
}
public static int[] SA(char[] T)
{
int n = T.Length;
int[] sa = new int[n];
SufSort(T, sa, n);
return sa;
}
public static int[] SA(int[] T, int alphabetSize)
{
int n = T.Length;
int[] sa = new int[n];
SufSort(T, sa, n, alphabetSize);
return sa;
}
public static int[] SA(string T)
{
return SA(T.ToArray());
}
// ---------------------------------------------------------------------
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace algorithms.strings
{
// ----- Suffix Automation -------------------------------------------------
//
// class Node
// void PutNext(char c, Node to)
// bool ContainsKeyNext(char c)
// Node GetNext(char c)
// List<string> Suffixes(char[] s)
//
// static SuffixAutomaton Build(char[] str)
// Node Extend(Node last, char c)
// SuffixAutomaton LexSort()
// SuffixAutomaton SortTopologically()
// long NumberOfDifferentSubstrings()
// string ToString()
// -------------------------------------------------------------------------
public class SuffixAutomaton
{
public class Node
{
public int id;
public int len;
public char key;
public Node link;
public Node[] next = new Node[3];
public Node original;
public int np = 0;
public int hit = 0;
public void PutNext(char c, Node to)
{
to.key = c;
if (hit << ~(c - 'a') < 0)
{
for (int i = 0; i < np; i++)
{
if (next[i].key == c)
{
next[i] = to;
return;
}
}
}
hit |= 1 << c - 'a';
if (np == next.Length)
{
Node[] next2 = new Node[np * 2];
Array.Copy(next, next2, next.Length);
next = next2;
}
next[np++] = to;
}
public bool ContainsKeyNext(char c)
{
return hit << ~(c - 'a') < 0;
}
public Node GetNext(char c)
{
if (hit << ~(c - 'a') < 0)
{
for (int i = 0; i < np; i++)
{
if (next[i].key == c) return next[i];
}
}
return null;
}
public List<string> Suffixes(char[] s)
{
List<string> list = new List<string>();
if (id == 0) return list;
int first = original != null ? original.len : len;
for (int i = link.len + 1; i <= len; i++)
{
list.Add(new string(s, first - i, i));
}
return list;
}
}
public Node t0;
public int len;
public Node[] nodes;
public int gen;
public bool sortedTopologically = false;
public bool lexsorted = false;
private SuffixAutomaton(int n)
{
gen = 0;
nodes = new Node[2 * n];
t0 = MakeNode(0, null);
}
private Node MakeNode(int len, Node original)
{
Node node = new Node();
node.id = gen;
node.original = original;
node.len = len;
nodes[gen++] = node;
return node;
}
public static SuffixAutomaton Build(char[] str)
{
int n = str.Length;
SuffixAutomaton sa = new SuffixAutomaton(n);
sa.len = str.Length;
Node last = sa.t0;
foreach (char c in str)
{
last = sa.Extend(last, c);
}
return sa;
}
public Node Extend(Node last, char c)
{
Node cur = MakeNode(last.len + 1, null);
Node p;
for (p = last; p != null && !p.ContainsKeyNext(c); p = p.link)
{
p.PutNext(c, cur);
}
if (p == null)
{
cur.link = t0;
}
else
{
Node q = p.GetNext(c);
if (p.len + 1 == q.len)
{
cur.link = q;
}
else
{
Node clone = MakeNode(p.len + 1, q);
clone.next = new Node[q.next.Length];
Array.Copy(q.next, clone.next, q.next.Length);
clone.hit = q.hit;
clone.np = q.np;
clone.link = q.link;
for (; p != null && q.Equals(p.GetNext(c)); p = p.link)
{
p.PutNext(c, clone);
}
q.link = cur.link = clone;
}
}
return cur;
}
class LexComparer : IComparer<Node>
{
public int Compare(Node a, Node b)
{
return a.key.CompareTo(b.key);
}
}
public SuffixAutomaton LexSort()
{
for (int i = 0; i < gen; i++)
{
Node node = nodes[i];
Array.Sort(node.next, 0, node.np, new LexComparer());
}
lexsorted = true;
return this;
}
public SuffixAutomaton SortTopologically()
{
int[] indeg = new int[gen];
for (int i = 0; i < gen; i++)
{
for (int j = 0; j < nodes[i].np; j++)
{
indeg[nodes[i].next[j].id]++;
}
}
Node[] sorted = new Node[gen];
sorted[0] = t0;
int p = 1;
for (int i = 0; i < gen; i++)
{
Node cur = sorted[i];
for (int j = 0; j < cur.np; j++)
{
if (--indeg[cur.next[j].id] == 0)
{
sorted[p++] = cur.next[j];
}
}
}
for (int i = 0; i < gen; i++) sorted[i].id = i;
nodes = sorted;
sortedTopologically = true;
return this;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
foreach (Node n in nodes)
{
if (n != null)
{
sb.Append(string.Format("{{id:{0}, len:{1}, link:{2}, cloned:{3}, ",
n.id,
n.len,
n.link != null ? n.link.id.ToString() : "",
n.original != null ? n.original.id.ToString() : ""
));
sb.Append("next:{{");
for (int i = 0; i < n.np; i++)
{
sb.Append(n.next[i].key + ":" + n.next[i].id + ",");
}
sb.Append("}}");
sb.Append("}}");
sb.Append("\n");
}
}
return sb.ToString();
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
namespace algorithms.strings
{
public static class SuffixAutomatonHacks
{
// ----- Suffix Automato Hacks -----------------------------------------
//
// Dependencies:
// -- Suffix Automaton
//
// bool find_substring(SuffixAutomaton sa, char[] a)
// void longest_common_substring(SuffixAutomaton sa, char[] a, out int pos, out int len)
// long number_of_different_substrings(char[] s)
// long total_length_of_different_substrings(char[] s)
// char[] least_cyclic_shift(char[] s)
// ---------------------------------------------------------------------
// bool test_find_substring(char[] s, char[] a)
// void test_longest_common_substring(char[] s, char[] a, out int pos, out int len)
// long test_number_of_different_substrings(char[] s)
// long test_total_length_of_different_substrings(char[] s)
// char[] test_least_cyclic_shift(char[] s)
// ---------------------------------------------------------------------
public static bool find_substring(SuffixAutomaton sa, char[] a)
{
SuffixAutomaton.Node v = sa.t0;
foreach (char c in a)
{
if (!v.ContainsKeyNext(c)) return false;
v = v.GetNext(c);
}
return true;
}
public static void longest_common_substring(SuffixAutomaton sa, char[] a, out int pos, out int len)
{
pos = 0;
len = 0;
SuffixAutomaton.Node v = sa.t0;
int l = 0;
for (int u = 0; u < a.Length; u++)
{
while (v != sa.t0 && !v.ContainsKeyNext(a[u]))
{
v = v.link;
l = v.len;
}
if (v.ContainsKeyNext(a[u]))
{
v = v.GetNext(a[u]);
l++;
}
if (l > len)
{
len = l; pos = u;
}
}
}
public static long number_of_different_substrings(char[] s)
{
SuffixAutomaton sa = SuffixAutomaton.Build(s);
if (!sa.sortedTopologically) sa.SortTopologically();
long[] D = new long[sa.gen];
for (int i = sa.gen - 1; i >= 0; i--)
{
D[i] = 1;
for (int j = 0; j < sa.nodes[i].np; j++)
D[i] += D[sa.nodes[i].next[j].id];
}
return D[0] - 1;
}
public static long total_length_of_different_substrings(char[] s)
{
SuffixAutomaton sa = SuffixAutomaton.Build(s);
if (!sa.sortedTopologically) sa.SortTopologically();
long[] D = new long[sa.gen];
long[] W = new long[sa.gen];
for (int i = sa.gen - 1; i >= 0; i--)
{
D[i] = 1;
for (int j = 0; j < sa.nodes[i].np; j++)
{
D[i] += D[sa.nodes[i].next[j].id];
W[i] += D[sa.nodes[i].next[j].id] + W[sa.nodes[i].next[j].id];
}
}
return W[0];
}
public static char[] least_cyclic_shift(char[] s)
{
char[] ss = new char[s.Length * 2];
Buffer.BlockCopy(s, 0, ss, 0, sizeof(char) * s.Length);
Buffer.BlockCopy(s, 0, ss, sizeof(char) * s.Length, sizeof(char) * s.Length);
SuffixAutomaton sa = SuffixAutomaton.Build(ss);
if (!sa.lexsorted) sa.LexSort();
SuffixAutomaton.Node v = sa.t0;
char[] a = new char[s.Length];
int ix = 0;
while (ix < s.Length)
{
v = v.next[0];
a[ix++] = v.key;
}
return a;
}
// ---------------------------------------------------------------------
public static bool test_find_substring(char[] s, char[] a)
{
return new string(s).IndexOf(new string(a)) > -1;
}
public static void test_longest_common_substring(char[] s, char[] a, out int pos, out int len)
{
pos = 0;
len = 0;
for (int l = Math.Min(s.Length, a.Length); l > 0; l--)
for (int u = 0; u < a.Length - l; u++)
{
int p = new string(s).IndexOf(new string(a).Substring(u, l));
if (p >= 0)
{
pos = p;
len = l;
return;
}
}
}
public static long test_number_of_different_substrings(char[] s)
{
HashSet<string> hs = new HashSet<string>();
for (int i = 0; i < s.Length; i++)
for (int len = 1; len <= s.Length - i; len++)
hs.Add(new string(s, i, len));
return hs.Count;
}
public static long test_total_length_of_different_substrings(char[] s)
{
HashSet<string> hs = new HashSet<string>();
long total = 0;
for (int i = 0; i < s.Length; i++)
for (int len = 1; len <= s.Length - i; len++) {
string ss = new string(s, i, len);
if (!hs.Contains(ss)) {
hs.Add(ss);
total += ss.Length;
}
}
return total;
}
public static char[] test_least_cyclic_shift(char[] s)
{
string a = new string(s);
for (int i = 1; i < s.Length; i++)
{
string b = a.Substring(i) + a.Substring(0, i);
if (string.Compare(a, b) == 1) a = b;
}
return a.ToCharArray();
}
// ---------------------------------------------------------------------
}
}